package cn.bellychang.leetcode.question450;

/**
 * Given a root node reference of a BST and a key,
 * delete the node with the given key in the BST.
 * <p>
 * Return the root node reference (possibly updated) of the BST.
 * <p>
 * Basically, the deletion can be divided into two stages:
 * 1. Search for a node to remove.
 * 2. If the node is found, delete the node.
 * <p>
 * Follow up: Can you solve it with time complexity O(height of tree)?
 * <p>
 * Constraints:
 * Each node has a unique value.
 *
 * @author ChangLiang
 * @date 2021/2/7
 */
public class Solution {

    public TreeNode deleteNode(TreeNode root, int key) {

        TreeNode curr = root;
        TreeNode parent = null;
        while (curr != null && curr.val != key) {
            parent = curr;
            if (curr.val > key) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        // 没找到
        if (curr == null) {
            return root;
        }

        // 处理root节点
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                root = null;
            } else if (root.left == null) {
                root = root.right;
            } else if (root.right == null) {
                root = root.left;
            } else {
                TreeNode minNode = getMinNodeFromRightTree(root);
                minNode.left = root.left;
                minNode.right = root.right;
                root = minNode;
            }
        }else {
            if (curr.left == null && curr.right == null) {
                if (parent.val > key) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            } else if (curr.left == null) {
                if (parent.val > curr.right.val) {
                    parent.left = curr.right;
                } else {
                    parent.right = curr.right;
                }
            } else if (curr.right == null) {
                if (parent.val > curr.left.val) {
                    parent.left = curr.left;
                } else {
                    parent.right = curr.left;
                }
            } else {
                TreeNode minNode = getMinNodeFromRightTree(curr);
                if (parent.val > minNode.val) {
                    parent.left = minNode;
                } else {
                    parent.right = minNode;
                }
                minNode.left = curr.left;
                minNode.right = curr.right;
            }
        }
        return root;
    }


    private TreeNode getMinNodeFromRightTree(TreeNode curr) {
        TreeNode min = curr.right;
        TreeNode minParent = curr;

        // 考虑后面没有左节点的情况
        if (min.left == null) {
            // 这里注意不能=null 进行连接
            curr.right = min.right;
            return min;
        }

        // 后面有左节点的情况
        while (min.left != null) {
            minParent = min;
            min = min.left;
        }
        // 注意不能=null 进行连接
        minParent.left = min.right;
        return min;
    }
}
